import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class prog {
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}





class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};




class Solution {
    public int getMaximumGenerated(int n){
        if(n<2){
            return n;
        }
        int sum=1;
        int[] arr=new int[n+1];
        arr[1]=1;
        for(int i=2;i<=n;i++){
            if((i&1)==1){
                arr[i]=arr[i/2]+arr[i/2+1];
                sum=Math.max(sum,arr[i]);
            }else{
                arr[i]=arr[i/2];
            }
        }
        return sum;
    }





    public int totalMoney(int n){
        if(n<8){
            return n*(n+1)/2;
        }
        int sum=0;
        int i=1;
        int j=7;
        while(n>=7){
            n-=7;
            sum+=(i+j)*(j-i+1);
            i++;
            j++;
        }
        sum/=2;
        while(n>0){
            sum+=i;
            n--;
            i++;
        }
        return sum;
    }





    public int maxDepth(Node root) {
        if(root==null){
            return 0;
        }
        int sum=1;
        for(Node n : root.children){
            sum=Math.max(sum,maxDepth(n)+1);
        }
        return sum;
    }






    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list=new ArrayList<>();
        constructPaths(root,"",list);
        return list;
    }
    public void constructPaths(TreeNode root,String str,List<String> list){
        if(root==null){
            return;
        }
        StringBuilder sb=new StringBuilder(str);
        sb.append(Integer.toString(root.val));
        if(root.left==null&&root.right==null){
            list.add(sb.toString());
        }else{
            sb.append("->");
            constructPaths(root.left,sb.toString(),list);
            constructPaths(root.right, sb.toString(), list);
        }
    }





    public String[] findRestaurant(String[] list1, String[] list2) {
        int mid=list1.length+ list2.length;
        List<Integer> list=new ArrayList<>();
        for(int i=0;i< list1.length;i++){
            for(int j=0;j< list2.length;j++){
                if(list1[i].equals(list2[j])){
                    if(i+j==mid){
                        list.add(i);
                    }
                    if(i+j<mid){
                        list.clear();
                        list.add(i);
                    }
                    mid=Math.min(mid,i+j);
                }
            }
        }
        String[] str=new String[list.size()];
        for(int i=0;i<list.size();i++){
            str[i]=list1[list.get(i)];
        }
        return str;
    }








    public int index=0;
    public TreeNode isBuildTree(int[] preorder,int[] inorder,int begin,int end){
        if(begin>end){
            return null;
        }
        TreeNode root=new TreeNode(preorder[index]);
        int rootIndex=findInorderIndex(inorder,begin,end,preorder[index]);
        index++;
        root.left=isBuildTree(preorder,inorder,begin,rootIndex-1);
        root.right=isBuildTree(preorder,inorder,rootIndex+1,end);
        return root;
    }
    public int findInorderIndex(int[] inorder,int begin,int end,int key){
        for(int i=begin;i<=end;i++){
            if(inorder[i]==key){
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||inorder==null){
            return null;
        }
        return isBuildTree(preorder,inorder,0,inorder.length-1);
    }





    public boolean isPalindrome(String s) {
        int left=0;
        int right=s.length()-1;
        while(left<right){
            char ch1=s.charAt(left);
            char ch2=s.charAt(right);
            if(!Character.isLetterOrDigit(ch1)){
                left++;
            }else if(!Character.isLetterOrDigit(ch2)){
                right--;
            }else{
                ch1=Character.toLowerCase(ch1);
                ch2=Character.toLowerCase(ch2);
                if(ch1!=ch2){
                    return false;
                }
                left++;
                right--;
            }
        }
        return true;
    }





    public boolean validPalindromes(String s) {
        int left=0;
        int right=s.length()-1;
        int count=0;
        while(left<right){
            if(s.charAt(left)!=s.charAt(right)){
                count++;
                if(count>1){
                    return false;
                }
            }
            left++;
            right--;
        }
        return true;
    }




    public boolean validPalindrome(String s) {
        int left=0;
        int right=s.length()-1;
        while(left<right){
            if(s.charAt(left)!=s.charAt(right)){
                return ispalindrome(s,left+1,right)||ispalindrome(s,left,right-1);
            }
            left++;
            right--;
        }
        return true;
    }
    public boolean ispalindrome(String s,int left,int right){
        while(left<right){
            if(s.charAt(left)!=s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }







    public boolean isAnagram(String s, String t) {
        if(s.length()==1&&t.length()==1){
            return false;
        }
        int[] arr=new int[26];
        for(int i=0;i<s.length();i++){
            arr[s.charAt(i)-'a']++;
        }
        for(int i=0;i<t.length();i++){
            arr[t.charAt(i)-'a']--;
            if(arr[t.charAt(i)-'a']<0){
                return false;
            }
        }
        for(int i=0;i<26;i++){
            if(arr[i]!=0){
                return false;
            }
        }
        return true;
    }






    public boolean isAlienSorted(String[] words, String order) {
        int[] arr=new int[26];
        for(int i=0;i<order.length();i++){
            arr[order.charAt(i)-'a']=i;
        }
        for(int i=0;i<words.length-1;i++){
            String s1=words[i];
            String s2=words[i+1];
            int len1=s1.length();
            int len2=s2.length();
            for(int j=0;j<Math.max(len1,len2);j++){
                int p=j>=len1?-1:arr[s1.charAt(j)-'a'];
                int q=j>=len2?-1:arr[s2.charAt(j)-'a'];
                if(p>q){
                    return false;
                }
                if(p<q){
                    break;
                }
            }
        }
        return true;
    }







    public int pivotIndex(int[] nums) {
        int count=0;
        for(int n : nums){
            count+=n;
        }
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            if(sum-nums[i]==count-sum){
                return i;
            }
        }
        return -1;
    }
}